//
//struct TreeNode {
//	int val;
//	struct TreeNode* left;
//	struct TreeNode* right;
//	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//};
//
//class Solution {
//public:
//
//	int lowestCommonAncestor(TreeNode* root, int p, int q) {
//		if (!root) return -1;
//		int val = root->val;
//		if (val > p && val > q)
//			return lowestCommonAncestor(root->left, p, q);
//		else if (val < p && val < q)
//			return lowestCommonAncestor(root->right, p, q);
//		else
//			return val;
//	}
//};
//
//int main()
//{
//	TreeNode* tree1 = new TreeNode(7);
//	TreeNode* tree2 = new TreeNode(1);
//	TreeNode* tree3 = new TreeNode(12);
//	TreeNode* tree4 = new TreeNode(0);
//	TreeNode* tree5 = new TreeNode(4);
//	TreeNode* tree6 = new TreeNode(11);
//	TreeNode* tree7 = new TreeNode(14);
//
//	tree1->left = tree2;
//	tree1->right = tree3;
//	tree2->left = tree4;
//	tree2->right = tree5;
//	tree3->left = tree6;
//	tree3->right = tree7;
//
//	Solution s;
//	int x;
//	x=s.lowestCommonAncestor(tree1, 1, 12);
//	return 0;
//}



struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
	ListNode* reverseList(ListNode* head)
	{
		if (!head) return nullptr;
		ListNode* prev = nullptr;
		ListNode* cur = head;
		while (cur->next)
		{
			ListNode* next = cur->next;
			cur->next = prev;
			prev = cur;
			cur = next;
		}
		return cur;
	}
};

int main()
{
	ListNode* node1 = new ListNode(1);
	ListNode* node2 = new ListNode(2);
	ListNode* node3 = new ListNode(3);
	ListNode* node4 = new ListNode(4);

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = nullptr;
	Solution s;
	s.reverseList(node1);
	return 0;
}